﻿// 0901train02.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <iostream>
#include <string>
#include <sstream>
#include <vector>
#include <algorithm>
#include <limits>
#include <unordered_map>
#include <unordered_set>

using namespace std;

/*
输入一个压缩后的报文，请返回它解压后的原始报文
压缩规则：n[str]，表示方括号内部的 str 正好重复 n 次

输入
3[k]2[mn]
输出
kkkmnmn

输入
3[m2[c]]
输出
mccmccmcc
 */
class Solution01
{
public:
    bool isChracter(char oh_char)
    {
        return oh_char >= 'a' && oh_char <= 'z';
    }

    bool isNum(char oh_char)
    {
        return oh_char >= '0' && oh_char <= '9';
    }
    Solution01(string&origin_str)
    {
        vector<string>stack_str_v;

        int curr_num = 0;
        string curr_str;

        for (int i=0; i<origin_str.size(); i++)
        {
            char oh_char = origin_str[i];
            if (isNum(oh_char))
            {
                curr_num = curr_num * 10 + oh_char - '0';
            }
            else if (isChracter(oh_char))
            {
                curr_str += oh_char;
            }
            else if (oh_char=='[')
            {
	            //1有字符串先推字符串，推完再推数字
                if (!curr_str.empty())
                {
                    stack_str_v.push_back(curr_str);
                    curr_str = "";
                }
                if (curr_num!=0)
                {
                    stack_str_v.push_back(to_string(curr_num));
                    curr_num = 0;
                }
            }
            else if (oh_char==']')
            {
                if (!curr_str.empty())
                {
                    stack_str_v.push_back(curr_str);
                    curr_str = "";
                }

                //1弹出栈顶字符串
                string top_str;
                while (!stack_str_v.empty() && !isNum(stack_str_v.back()[0]))
                {
                    top_str = stack_str_v.back()+top_str;
                    stack_str_v.pop_back();
                }

                string repeat_str;
                if (!stack_str_v.empty()&&isNum(stack_str_v.back()[0]))
                {
                    //弹出栈顶数字，累加
                    string num_str = stack_str_v.back();
                    stack_str_v.pop_back();

                    int count = stoi(num_str);
                    
                    while (count--)
                    {
                        repeat_str += top_str;
                    }
                }
                
                if (repeat_str.empty())
                {
                    stack_str_v.push_back(top_str);
                }
                else
                {
                    stack_str_v.push_back(repeat_str);
                }
                
                //else if (oh_char==')')
            }
            
        }

        string result;
        for (auto&str:stack_str_v)
        {
            result += str;
        }
        cout << result;
        //Solution01
    }
};


/*
 现需要实现一种算法，能将一组压缩字符串还原成原始字符串，还原规则如下：
1. 字符后面加数字 N，表示重复字符 N 次。例如：压缩内容为 A3，表示原始字符串为 AAA
2. 花括号中的字符串加数字 N，表示花括号中的字符串重复 N 次
例如：压缩内容为{AB}3，表示原始字符串为 ABABAB
3. 字符加 N 和花括号后面加 N，支持任意的嵌套，包括互相嵌套
例如：压缩内容可以{A3B1{C}3}3
输入描述
输入一行压缩后的字符串
输出描述
输出压缩前的字符串
说明
输入输出的字符串区分大小写

输入
A3
输出
AAA

输入
{A3B1{C}3}3
输出
AAABCCCAAABCCCAAABCCC

{A3B1{C}3}3 代表 A 字符重复 3 次
B 字符重复 1 次
花括号中的 C 字符重复 3 次
最外层花括号中的 AAABCCC 重复 3 次

1左括号直接入栈
2字母直接入栈
3数字，如果下一位不是数字了，那么弹出栈顶字母做累加，清空
4左括号，入栈，字母入栈
右括号，把栈里字母全部取出拼接，直到遇到左括号
拼完塞回去
数字，弹出栈顶字母累加，塞回去
右括号
 */

class Solution02
{
public:
    bool isCharacter(char oh_char)
    {
        bool is_bigger = oh_char >= 'A' && oh_char <= 'Z';
        bool is_small = oh_char >= 'a' && oh_char <= 'z';

        return is_bigger||is_small;
    }
    bool isNum(char oh_char)
    {
        return oh_char >= '0' && oh_char <= '9';
    }

    Solution02(string&origin_str)
    {
        int curr_num = 0;
        vector<string>stack_str_v;

        for (int i=0; i<origin_str.size(); i++)
        {
            char curr_char = origin_str[i];
            if (isCharacter(curr_char))
            {
                string tmp_str;
                tmp_str += curr_char;
                stack_str_v.push_back(tmp_str);
            }
            else if (isNum(curr_char))
            {
                if (i!=origin_str.size()-1 && isNum(origin_str[i+1]))
                {
                    curr_num = curr_num * 10 + curr_char - '0';
                }
                else
                {
                    if (curr_num!=0)
                    {
                        curr_num = curr_num * 10 + curr_char - '0';
                    }
                    else
                    {
                        curr_num = curr_char - '0';
                    }
	                
                    string top_str = stack_str_v.back();
                    stack_str_v.pop_back();
                    string repeat_str;
                    while (curr_num--)
                    {
                        repeat_str += top_str;
                    }
                    stack_str_v.push_back(repeat_str);
                    curr_num = 0;
                }

            }
            else if (curr_char=='{')
            {
                //左括号直接入栈
                string tmp_str;
                tmp_str += curr_char;
                stack_str_v.push_back(tmp_str);
            }
            else if (curr_char=='}')
            {
                string combine_str;
                while (stack_str_v.back()!="{")
                {
                    combine_str = stack_str_v.back()+ combine_str;
                    stack_str_v.pop_back();
                }
                //pop左括号
                stack_str_v.pop_back();

                stack_str_v.push_back(combine_str);

            }

            //for------
        }

        string result;
        for (auto&str:stack_str_v)
        {
            result += str;
        }
        cout << result;
        //Solution02
    }
};

int main()
{
	{
        //A3
        //{A3B1{C}3}3
        string input = "{{A3B1{C}3}3}10";
        //string input;
        //getline(cin, input);
        Solution02 solu(input);
        return 0;
	}
    //3[k]2[mn]
    //3[m2[c]]
    //3[m2[2[c]]]
    //2[2[dq3[3[a]4[v]5[u]6[p]]]9[io]]
    string input = "3[m2[2[c]]]";
    //string input;
    //getline(cin, input);
    Solution01 solu(input);

}

// 运行程序: Ctrl + F5 或调试 >“开始执行(不调试)”菜单
// 调试程序: F5 或调试 >“开始调试”菜单

// 入门使用技巧: 
//   1. 使用解决方案资源管理器窗口添加/管理文件
//   2. 使用团队资源管理器窗口连接到源代码管理
//   3. 使用输出窗口查看生成输出和其他消息
//   4. 使用错误列表窗口查看错误
//   5. 转到“项目”>“添加新项”以创建新的代码文件，或转到“项目”>“添加现有项”以将现有代码文件添加到项目
//   6. 将来，若要再次打开此项目，请转到“文件”>“打开”>“项目”并选择 .sln 文件
